// https://leetcode.cn/problems/path-sum-iii/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 前缀和+DFS统计二叉树路径和等于目标值的路径数量
// 2. 哈希表记录从根节点到当前节点的前缀和出现次数
// 3. 查找goal = currentSum - targetSum是否存在于哈希表
// 4. DFS回溯时正确恢复哈希表和当前和的状态
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    int ret;
    long long sum;
    unordered_map<long long, int> hash;

    int pathSum(TreeNode* root, int targetSum) 
    {
        if (root == nullptr) return 0;

        ret = 0, sum = 0;
        hash.clear();
        
        hash[0LL] = 1;

        recur(root, targetSum);

        return ret;
    }

    void recur(TreeNode* root, int targetSum)
    {
        if (root == nullptr)
        {
            return ;
        }

        sum += root->val;
        long long goal = sum - targetSum;
        if (hash.count(goal) > 0)
        {
            ret += hash[goal];
        }
        hash[sum]++;

        recur(root->left, targetSum);
        recur(root->right, targetSum);

        if (--hash[sum] == 0)
        {
            hash.erase(sum);
        }
        sum -= root->val;

        return ;
    }
};

int main()
{
    vector<string> tree1 = {"10","5","-3","3","2","null","11","3","-2","null","1"};
    vector<string> tree2 = {"5","4","8","11","null","13","4","7","2","null","null","5","1"};
    int targetSum1 = 8, targetSum2 = 22; 
    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    cout << sol.pathSum(root1, targetSum1) << endl;
    cout << sol.pathSum(root2, targetSum2) << endl;

    return 0;
}